Problèmes d'ordonnancement sur machines parallèles avec tâches communicantes et indisponibilités.
Identifieur interne : 000276 ( France/Analysis ); précédent : 000275; suivant : 000277Problèmes d'ordonnancement sur machines parallèles avec tâches communicantes et indisponibilités.
Auteurs : Eric Sanlaville [France] ; Frédéric Guinand [France] ; Amine Mahjoub [Tunisie]Source :
Descripteurs français
Abstract
En gestion de production comme en informatique parallèle, les tâches à exécuter sont souvent liées par des précédences qui entraînent des délais de communication ou de transport. De la même manière, les machines exécutant ces tâches ne sont pas toujours disponibles, pour des raisons diverses : maintenance, panne, apparition de tâches prioritaires. Ces deux types de problèmes d'ordonnancement ont été étudiés indépendamment, mais aucun travail ne les considère simultanément, même pour le critère de minimisation de la durée totale.
Dans le premier cas, le problème central est l'ordonnancement unitaire (UECT : Unit Execution and Communication Times). Le problème est pseudo polynomial si le graphe de précédence est un arbre. Dans le cas 2 machines, plusieurs algorithmes indépendants existent. Celui proposé par Guinand a une caractéristique intéressante : toutes les communications vont d'une machine vers l'autre (ordonnancement processeur-ordonné). Ceci permet de limiter grandement l'impact de délais de communications différents des valeurs prévues.
Dans le second cas, de nombreuses études considèrent des tâches indépendantes. Des résultats existent pour des graphes de précédence, là encore dans le cas de durées unitaires. En particulier, l'algorithme de Coffman et Graham (algorithme de liste) reste optimal sur deux machines en présence de périodes d'indisponibilités.
Si l'on considère l'ordonnancement d'arbres de tâches unitaires avec communications unitaires et indisponibilités, des difficultés surgissent même pour 2 machines : les algorithmes processeur-ordonnés ne sont plus dominants, et les algorithmes classiques (comme ceux de Coffma et Graham ou de Lawler) non plus. Nous proposons néanmoins un algorithme reprenant les idées de l'algorithme de Guinand , notamment en considérant en bloc l'ordonnancement de sous-arbres. La complexité de cet algorithme et des problèmes avec communications et indisponibilités est discutée. Des résultats expérimentaux complètent cet exposé.
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000701
- to stream Hal, to step Curation: 000701
- to stream Hal, to step Checkpoint: 000164
- to stream Main, to step Merge: 000289
- to stream Main, to step Curation: 000288
- to stream Main, to step Exploration: 000288
- to stream France, to step Extraction: 000276
Links to Exploration step
Hal:hal-00946386Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr">Problèmes d'ordonnancement sur machines parallèles avec tâches communicantes et indisponibilités.</title>
<author><name sortKey="Sanlaville, Eric" sort="Sanlaville, Eric" uniqKey="Sanlaville E" first="Eric" last="Sanlaville">Eric Sanlaville</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-244557" status="INCOMING"><orgName>Normandie Université - LITIS</orgName>
<orgName type="acronym">LITIS</orgName>
<desc><address><addrLine>25, rue Philippe Lebon BP 540 - 76058 Le Havre Cedex - France</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
</affiliation>
</author>
<author><name sortKey="Guinand, Frederic" sort="Guinand, Frederic" uniqKey="Guinand F" first="Frédéric" last="Guinand">Frédéric Guinand</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-244557" status="INCOMING"><orgName>Normandie Université - LITIS</orgName>
<orgName type="acronym">LITIS</orgName>
<desc><address><addrLine>25, rue Philippe Lebon BP 540 - 76058 Le Havre Cedex - France</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
</affiliation>
</author>
<author><name sortKey="Mahjoub, Amine" sort="Mahjoub, Amine" uniqKey="Mahjoub A" first="Amine" last="Mahjoub">Amine Mahjoub</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-244558" status="INCOMING"><orgName>UTIC</orgName>
<orgName type="acronym">UTIC</orgName>
<desc><address><addrLine>Unite de Recherche UTIC. Ecole Supérieure des Sciences et Techniques de Tunis 5 Avenue Taha Hussein, BP 56, Beb Manara, Tunis.</addrLine>
<country key="TN"></country>
</address>
</desc>
<listRelation><relation active="#struct-358462" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-358462" type="direct"><org type="institution" xml:id="struct-358462" status="INCOMING"><orgName>UTIC</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Tunisie</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00946386</idno>
<idno type="halId">hal-00946386</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00946386</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00946386</idno>
<date when="2014-02-26">2014-02-26</date>
<idno type="wicri:Area/Hal/Corpus">000701</idno>
<idno type="wicri:Area/Hal/Curation">000701</idno>
<idno type="wicri:Area/Hal/Checkpoint">000164</idno>
<idno type="wicri:Area/Main/Merge">000289</idno>
<idno type="wicri:Area/Main/Curation">000288</idno>
<idno type="wicri:Area/Main/Exploration">000288</idno>
<idno type="wicri:Area/France/Extraction">000276</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="fr">Problèmes d'ordonnancement sur machines parallèles avec tâches communicantes et indisponibilités.</title>
<author><name sortKey="Sanlaville, Eric" sort="Sanlaville, Eric" uniqKey="Sanlaville E" first="Eric" last="Sanlaville">Eric Sanlaville</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-244557" status="INCOMING"><orgName>Normandie Université - LITIS</orgName>
<orgName type="acronym">LITIS</orgName>
<desc><address><addrLine>25, rue Philippe Lebon BP 540 - 76058 Le Havre Cedex - France</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
</affiliation>
</author>
<author><name sortKey="Guinand, Frederic" sort="Guinand, Frederic" uniqKey="Guinand F" first="Frédéric" last="Guinand">Frédéric Guinand</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-244557" status="INCOMING"><orgName>Normandie Université - LITIS</orgName>
<orgName type="acronym">LITIS</orgName>
<desc><address><addrLine>25, rue Philippe Lebon BP 540 - 76058 Le Havre Cedex - France</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation><relation active="#struct-300317" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Le Havre</settlement>
<region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
</placeName>
<orgName type="university">Université du Havre</orgName>
</affiliation>
</author>
<author><name sortKey="Mahjoub, Amine" sort="Mahjoub, Amine" uniqKey="Mahjoub A" first="Amine" last="Mahjoub">Amine Mahjoub</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-244558" status="INCOMING"><orgName>UTIC</orgName>
<orgName type="acronym">UTIC</orgName>
<desc><address><addrLine>Unite de Recherche UTIC. Ecole Supérieure des Sciences et Techniques de Tunis 5 Avenue Taha Hussein, BP 56, Beb Manara, Tunis.</addrLine>
<country key="TN"></country>
</address>
</desc>
<listRelation><relation active="#struct-358462" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-358462" type="direct"><org type="institution" xml:id="struct-358462" status="INCOMING"><orgName>UTIC</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Tunisie</country>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>algorithme exact</term>
<term>communications</term>
<term>indisponibilités</term>
<term>ordonnancement</term>
<term>précédences</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="fr">En gestion de production comme en informatique parallèle, les tâches à exécuter sont souvent liées par des précédences qui entraînent des délais de communication ou de transport. De la même manière, les machines exécutant ces tâches ne sont pas toujours disponibles, pour des raisons diverses : maintenance, panne, apparition de tâches prioritaires. Ces deux types de problèmes d'ordonnancement ont été étudiés indépendamment, mais aucun travail ne les considère simultanément, même pour le critère de minimisation de la durée totale.
Dans le premier cas, le problème central est l'ordonnancement unitaire (UECT : Unit Execution and Communication Times). Le problème est pseudo polynomial si le graphe de précédence est un arbre. Dans le cas 2 machines, plusieurs algorithmes indépendants existent. Celui proposé par Guinand a une caractéristique intéressante : toutes les communications vont d'une machine vers l'autre (ordonnancement processeur-ordonné). Ceci permet de limiter grandement l'impact de délais de communications différents des valeurs prévues.
Dans le second cas, de nombreuses études considèrent des tâches indépendantes. Des résultats existent pour des graphes de précédence, là encore dans le cas de durées unitaires. En particulier, l'algorithme de Coffman et Graham (algorithme de liste) reste optimal sur deux machines en présence de périodes d'indisponibilités.
Si l'on considère l'ordonnancement d'arbres de tâches unitaires avec communications unitaires et indisponibilités, des difficultés surgissent même pour 2 machines : les algorithmes processeur-ordonnés ne sont plus dominants, et les algorithmes classiques (comme ceux de Coffma et Graham ou de Lawler) non plus. Nous proposons néanmoins un algorithme reprenant les idées de l'algorithme de Guinand , notamment en considérant en bloc l'ordonnancement de sous-arbres. La complexité de cet algorithme et des problèmes avec communications et indisponibilités est discutée. Des résultats expérimentaux complètent cet exposé.
</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>Tunisie</li>
</country>
<region><li>Haute-Normandie</li>
<li>Région Normandie</li>
</region>
<settlement><li>Le Havre</li>
</settlement>
<orgName><li>Université du Havre</li>
</orgName>
</list>
<tree><country name="France"><region name="Région Normandie"><name sortKey="Sanlaville, Eric" sort="Sanlaville, Eric" uniqKey="Sanlaville E" first="Eric" last="Sanlaville">Eric Sanlaville</name>
</region>
<name sortKey="Guinand, Frederic" sort="Guinand, Frederic" uniqKey="Guinand F" first="Frédéric" last="Guinand">Frédéric Guinand</name>
</country>
<country name="Tunisie"><noRegion><name sortKey="Mahjoub, Amine" sort="Mahjoub, Amine" uniqKey="Mahjoub A" first="Amine" last="Mahjoub">Amine Mahjoub</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000276 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000276 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/France |area= LeHavreV1 |flux= France |étape= Analysis |type= RBID |clé= Hal:hal-00946386 |texte= Problèmes d'ordonnancement sur machines parallèles avec tâches communicantes et indisponibilités. }}
This area was generated with Dilib version V0.6.25. |